package top.humbleyuan.mock;





import org.junit.Test;

import java.util.*;

/**
 * @Author HumbleYuan
 * @Date 2020/3/23 20:07
 * @Des 相关题目备用
 */
public class Mock {
    public static void main(String[] args) {
        // 1. 判断多少回文子串
        //back();

        // 2. 成绩排序，对象存储
        //sortByGrade();

        // 3. 编辑距离，计算相似度
        similarity();
    }

    /**
     * 判断一共有多少回文子串
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串（回文串是一个正读和反读都一样的字符串）。
     * 具有不同开始位置或结束位置的回文串，即使是由相同的字符组成，也会被计为是不同的子串。
     * abc:
     * 3
     */
    public static void back() {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            String s = sc.nextLine();
            int num = 0;
            
            // 暴力
            for (int i = 0; i < s.length() - 1; i++) {
                for (int j = 2; j <= s.length() - i; j++) {
                    String curS = s.substring(i, i + j);

                    StringBuilder rsBuilder = new StringBuilder(curS);
                    String rs = rsBuilder.reverse().toString();
                    if(rs.equals(curS)) {
                        num ++;
                    }
                }
            }
            num += s.length();
            System.out.println(num);
        }
    }

    /**
     * 学生：学号 + 成绩
     * 按成绩排序输出信息
     */
    public static void sortByGrade() {
        Scanner sc = new Scanner(System.in);
        List<Student> list = new ArrayList<>();

        while (sc.hasNext()) {
            int num = Integer.valueOf(sc.nextLine());
            Student s11 = new Student(1,2);

            for (int i = 0; i < num; i++) {
                String[] s = sc.nextLine().split(" ");
                Student student = new Student(Integer.valueOf(s[0]),Integer.valueOf(s[1]));
                list.add(student);
            }

            list.sort((s1,s2) -> {
                return s1.grade < s2.grade ? -1 : 1;
            });

            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i).number + " " + list.get(i).grade);
            }


        }

    }
    static class Student {
        private int number;
        private int grade;

        public Student(int number,int grade){
            this.number = number;
            this.grade = grade;
        }

    }

    /**
     * DP
     * 计算字符串相似度(编辑距离)：
     * 增删改一个字符相当于距离d加1，相似度 = 1 / (d + 1)
     * 如：abc abcc : 1/2
     *    a   abc  : 1/3
     */
    public static void similarity() {
        Scanner sc = new Scanner(System.in);

        /**
         * 递推：从子问题开始求解，用二维数组存储子串状态
         * 1. 设串s1,s2,若某一个串为空那么，距离 = 另一个串长度,即初始化边界条件
         * 2. 若当前比较字符相同，那么d[i][j] = d[i-1]d[j-1],相当于同时加上同一个字符，距离上没有增加
         * 3. 若不同，分三种情况,实例说明：
         *      h   a   v   e
         *   0  1   2   3   4
         * v 1  1
         *
         * e 2
         *
         * a 3
         *      子串v变成h,d[1][1]
         *      3.1 从h -> v,即d[i-1][j] = d[0][1] + 1,表示h -> ""d = 1,
         *          那么再从"" -> v,距离加1，即d = d[i-1][j] + 1;
         *          h -> v => h -> "" -> v
         *      3.2 从v -> h,类似 d = d[i][j-1] + 1;
         *      3.3 从"" -> "", d = d[0][0] = 0,那么h -> v只需将h变成v,即d[i-1][j-1] + 1
         *
         *      递推：
         *      d[i][j] = min[d[i-1][j-1] + (c1 == c2 ? 0 : 1),
         *                      d[i-1][j] + 1,
         *                      d[i][j-1] + 1]
         */
        while (sc.hasNext()) {
            String s1 = sc.nextLine();
            String s2 = sc.nextLine();

            int[][] dis = new int[s1.length() + 1][s2.length() + 1];

            // 初始化边界值
            for (int i = 1; i <= s1.length(); i++) {
                dis[i][0] = i;
            }

            for (int i = 1; i <= s2.length(); i++) {
                dis[0][i] = i;
            }

            // 以列为外层循环
            for (int i = 1; i <= s1.length(); i++) {
                for (int j = 1; j <= s2.length(); j++) {
                    int replaceDis = 1;
                    // 字符相同
                    if(s1.charAt(i-1) == s2.charAt(j-1)) {
                        replaceDis = 0;
                    }

                    dis[i][j] = Math.min(dis[i-1][j-1] + replaceDis,
                            Math.min(dis[i-1][j], dis[i][j-1]) + 1);
                }
            }

            // 只算距离
            System.out.println(dis[s1.length()][s2.length()]);
        }
    }


    /**
     * 美团
     * 表达式判断
     * 给出一个布尔表达式的字符串，比如：true or false and false，表达式只包含true，false，and和or，
     * 现在要对这个表达式进行布尔求值，计算结果为真时输出true、为假时输出false，不合法的表达时输出error（比如：true true）。
     * 表达式求值是注意and 的优先级比 or 要高，
     * 比如：true or false and false，等价于 true or (false and false)，计算结果是 true。
     */

    public static void meituan_1() {
        Scanner sc = new Scanner(System.in);
        String[] words = sc.nextLine().split(" ");

        if(words.length == 1 && words[0].length() <= 3) {
            System.out.println("error");
        }

        boolean res = true;

        // 先走一遍找所有and
        for(int i = 1;i < words.length; i += 2) {
            if(words[1].length() > 3) {
                System.out.println("error");
                return;
            }

            // 前后不对
            if(words[i-1].length() <= 3 || i == words.length - 1 ||
                    words[i + 1].length() <= 3) {
                System.out.println("error");
                return;
            }

            if("and".equals(words[i])) {

                if(!("true").equals(words[i-1]) && ("true").equals(words[i+1])) {
                    words[i+1] = "false";
                }

                String[] newS = new String[words.length - 2];
                // 前半部分
                System.arraycopy(words, 0, newS, 0, i - 1);
                // 后半部分
                System.arraycopy(words, i+1, newS, i - 1, words.length - i - 1);
                i -= 2;
                words = newS;

            }
        }

        // 全是or也不会有error,有true就是true
        if(Arrays.asList(words).contains("true")) {
            System.out.println(true);
        }else {
            System.out.println(false);
        }

    }


    /**
     * 美团,模式串
     *
     * @param
     */

    public static void meituan_2() {
        // 1.遍历模式串，找到第一个对应为不等的
        // 2.  2.1 ? 直接替换目标串中对应字符
        //     2.2 * 从目标串当前位置向后知道找到与模式串当前位置后一个字符相同为止，替换字符段
        // 3. 重复1
        Scanner sc = new Scanner(System.in);
        char[] s1 = sc.nextLine().toCharArray();
        char[] s2 = sc.nextLine().toCharArray();
        for(int i = 0;i < s1.length;i++) {
            if(s1[i] != s2[i]) {
                if(s1[i] == '?') {
                    s1[i] = s2[i];
                }else if(s1[i] == '*') {
                    int j;
                    for(j = i;j < s2.length;j++) {
                        if(s2[j] == s1[i+1]) {
                            break;
                        }
                    }

                    if(j == s2.length) {
                        System.out.println(0);
                        return;
                    }
                    // 复制长度
                    s1 = s1.toString().replaceFirst("*", Arrays.copyOfRange(s2, i, j).toString()).toCharArray();
                    i = j;
                }else {
                    System.out.println(0);
                    return;
                }
            }
        }

        System.out.println(1);
    }

    /**
     * 无序数组找中位数
     */
    @Test
    public void median() {
        // 改写快排
        int[] nums = {5,2,78,54,23,12};


        /**
         * 奇数：
         * index == mid => break;
         * index < mid => partition(index + 1, end)
         * index > mid => partition(begin, index - 1);
         *
         * 偶数：mid1 = length / 2 - 1; mid2 = length / 2
         * index == mid1 => nums[index + 1]之后最小值  index == mid2类似
         * index < mid1 => partition(index + 1, end)
         * index > mid2 => partition(begin, index - 1)
         */
        int base = 0;
        int begin = 0, end = nums.length - 1;
        int res;

        // 奇数
        if(nums.length % 2 == 1) {
            int mid = nums.length / 2;

            while(mid != base) {
                base = partition(nums, begin, end);

                if(base == mid) {
                    break;
                }

                if(base < mid) {
                    begin = base + 1;
                } else {
                    end = base - 1;
                }
            }

            res = nums[base];

        } else {
            int mid1 = nums.length / 2 - 1;
            int mid2 = mid1 + 1;

            while(base != mid1 && base != mid2) {
                base = partition(nums, begin, end);

                if(base == mid1 || base == mid2) {
                    break;
                }

                if(base < mid1) {
                    begin = base + 1;
                } else if(base > mid2) {
                    end = base - 1;
                }
            }

            // 找第二个中间值
            if(base == mid1) {
                int nBegin = base + 1;
                while(base != mid2) {
                    base = partition(nums, nBegin, end);

                    if(base == mid2) {
                        break;
                    }

                    end = base - 1;
                }
            } else {
                int nEnd = base - 1;
                while (base != mid1) {
                    base = partition(nums, begin, nEnd);

                    if(base == mid1) {
                        break;
                    }

                    begin = base + 1;
                }
            }

            res = (nums[mid1] + nums[mid2]) >> 1;
        }

        System.out.println(res);
    }

    public int partition(int[] nums, int begin, int end) {
        int base = nums[begin];

        int i = begin, j = end;

        while (i < j) {

            // 基准选最左，就要从右边开始
            while(nums[j] >= base && i < j) {
                j--;
            }

            while (nums[i] <= base && i < j) {
                i++;
            }

            // 交换
            if(i < j) {
                swap(i, j, nums);
            }

        }

        swap(begin, i, nums);
        return i;

    }

    public void swap(int i, int j,int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    /**
     * 无序找中位数，使用Priority(相当于大顶堆和小顶堆)
     */
    @Test
    public void median_2() {
        int[] nums = {5, 2, 78, 54, 23, 45};

        int res;

        PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length / 2 + 1, (n1, n2) -> {
            return n2 - n1;
        });

        for (int i = 0; i < nums.length; i++) {
            if(queue.size() < nums.length / 2 + 1) {
                queue.offer(nums[i]);
            } else {
                if(queue.peek() > nums[i]) {
                    // 大顶堆，拿走最大元素
                    queue.poll();
                    queue.offer(nums[i]);
                }

            }

        }

        if(nums.length % 2 == 1) {
            res = queue.poll();
        } else {
            int num1 = queue.poll();
            int num2 = queue.poll();
            res = (num1 + num2) / 2;
        }

        System.out.println(res);
    }

    /**
     * 合并金币堆，最小花费(2堆合并)
     */
    @Test
    public void mergeCoin(){
        // 合并金币堆，最小花费
        // merge();
    }

    private static void merge() {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            int num = Integer.valueOf(sc.nextLine());

            String[] nums = sc.nextLine().split(" ");
            int[] sums = getSum(nums);


            int[][] cost = new int[num][num];

            // 动态规划
            for(int len = 2;len <= num;len++) {
                for(int begin = 0;begin <= num - len;begin ++) {
                    int end = begin + len -1;

                    int min = -1;
                    for(int k = begin; k < end; k++) {

                        int temp = cost[begin][k] + cost[k+1][end] +
                                (sums[end] - (begin == 0 ? 0 : sums[begin - 1]));

                        if(min == -1 || min > temp) {
                            min = temp;
                        }
                    }
                    cost[begin][end] = min;
                }
            }
            System.out.println(cost[0][num-1]);
        }
    }

    // 计算下标i及之前所有元素和
    public static int[] getSum(String[] nums) {
        int[] sum = new int[nums.length];
        for(int i = 0;i < nums.length;i++) {
            sum[i] = (i == 0 ? 0 : sum[i-1]) + Integer.valueOf(nums[i]);
        }
        return sum;
    }


}
